<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.2.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">


<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">
  <link rel="stylesheet" href="/lib/pace/pace-theme-minimal.min.css">
  <script src="/lib/pace/pace.min.js"></script>

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"sekla.cn","root":"/","scheme":"Muse","version":"7.8.0","exturl":false,"sidebar":{"position":"right","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":"valine","storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":false,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
  </script>

  <meta name="description" content="Search treesAVL树概述AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。找、插入和删除在平均和最坏情况下的时间复杂度都是$O(logn)$。增加和删除元素的操作则可能需要借由一次或多次树旋转(可以理解为旋转操作前后，树的中序遍历不变)，让树重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和">
<meta property="og:type" content="article">
<meta property="og:title" content="树的一些总结">
<meta property="og:url" content="http://sekla.cn/2021/04/14/datas-tree/index.html">
<meta property="og:site_name" content="Sekla&#39;s Blog">
<meta property="og:description" content="Search treesAVL树概述AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。找、插入和删除在平均和最坏情况下的时间复杂度都是$O(logn)$。增加和删除元素的操作则可能需要借由一次或多次树旋转(可以理解为旋转操作前后，树的中序遍历不变)，让树重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://i.loli.net/2021/04/14/aMqFZHXixgetEG8.png">
<meta property="og:image" content="https://i.loli.net/2021/04/14/Vg9KH5QuwEo6I41.png">
<meta property="og:image" content="https://i.loli.net/2021/04/14/Sg9yurwdxULeD2k.png">
<meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Binomial_Trees.svg/500px-Binomial_Trees.svg.png">
<meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/6/61/Binomial-heap-13.svg/325px-Binomial-heap-13.svg.png">
<meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/9/9f/Binomial_heap_merge1.svg/200px-Binomial_heap_merge1.svg.png">
<meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Suffix_tree_BANANA.svg/250px-Suffix_tree_BANANA.svg.png">
<meta property="og:image" content="https://i.loli.net/2021/04/14/niDsg7rYXcMVBRq.png">
<meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/d/d1/Segment_tree.svg/420px-Segment_tree.svg.png">
<meta property="article:published_time" content="2021-04-14T04:39:04.000Z">
<meta property="article:modified_time" content="2021-10-18T14:44:32.553Z">
<meta property="article:author" content="Sekla">
<meta property="article:tag" content="C++">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://i.loli.net/2021/04/14/aMqFZHXixgetEG8.png">

<link rel="canonical" href="http://sekla.cn/2021/04/14/datas-tree/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>树的一些总结 | Sekla's Blog</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

  <script type="text/javascript" src="/js/my_js/clicklove.js"></script>
<!-- hexo injector head_end start -->
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/katex.min.css">

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/hexo-math@4.0.0/dist/style.css">
<!-- hexo injector head_end end --></head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">Sekla's Blog</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
      <p class="site-subtitle" itemprop="description">Keep Learning Keep Doing</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签<span class="badge">14</span></a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类<span class="badge">23</span></a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档<span class="badge">100</span></a>

  </li>
  </ul>
</nav>




</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>
  <div class="reading-progress-bar"></div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://sekla.cn/2021/04/14/datas-tree/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="Sekla">
      <meta itemprop="description" content="Sekla">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Sekla's Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          树的一些总结
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              <time title="创建时间：2021-04-14 12:39:04" itemprop="dateCreated datePublished" datetime="2021-04-14T12:39:04+08:00">2021-04-14</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2021-10-18 22:44:32" itemprop="dateModified" datetime="2021-10-18T22:44:32+08:00">2021-10-18</time>
              </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-folder"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">数据结构与算法</span></a>
                </span>
                  ，
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" itemprop="url" rel="index"><span itemprop="name">数据结构</span></a>
                </span>
            </span>

          
            <span class="post-meta-item" title="阅读次数" id="busuanzi_container_page_pv" style="display: none;">
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              <span class="post-meta-item-text">阅读次数：</span>
              <span id="busuanzi_value_page_pv"></span>
            </span><br>
            <span class="post-meta-item" title="本文字数">
              <span class="post-meta-item-icon">
                <i class="far fa-file-word"></i>
              </span>
                <span class="post-meta-item-text">本文字数：</span>
              <span>14k</span>
            </span>
            <span class="post-meta-item" title="阅读时长">
              <span class="post-meta-item-icon">
                <i class="far fa-clock"></i>
              </span>
                <span class="post-meta-item-text">阅读时长 &asymp;</span>
              <span>13 分钟</span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h1 id="Search-trees"><a href="#Search-trees" class="headerlink" title="Search trees"></a>Search trees</h1><h1 id="AVL树"><a href="#AVL树" class="headerlink" title="AVL树"></a>AVL树</h1><h2 id="概述"><a href="#概述" class="headerlink" title="概述"></a>概述</h2><p>AVL树是最早被发明的<strong>自平衡二叉查找树</strong>。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为<strong>高度平衡树</strong>。找、插入和删除在平均和最坏情况下的时间复杂度都是$O(logn)$。增加和删除元素的操作则可能需要借由一次或多次树旋转(可以理解为旋转操作前后，树的中序遍历不变)，让树重新平衡。AVL树得名于它的发明者<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/%E6%A0%BC%E5%A5%A5%E5%B0%94%E5%90%89%C2%B7%E9%98%BF%E6%9D%B0%E5%B0%94%E6%9D%BE-%E9%9F%A6%E5%88%A9%E6%96%AF%E5%9F%BA">G. M. Adelson-Velsky</a>和<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/w/index.php?title=Evgenii_Landis&action=edit&redlink=1">Evgenii Landis</a>，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。</p>
<p><strong>最小不平衡子树</strong>：距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树。</p>
<p><img src="https://i.loli.net/2021/04/14/aMqFZHXixgetEG8.png" alt="AVL_1.png"></p>
<p>节点的<strong>平衡因子</strong>是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。</p>
<p>AVL必须满足2个条件</p>
<p>1.必须是BST。</p>
<p>2.每个节点的左子树和右子树高度差最多为1.</p>
<a id="more"></a>

<h2 id="数据结构"><a href="#数据结构" class="headerlink" title="数据结构"></a>数据结构</h2><h3 id="基于BST实现"><a href="#基于BST实现" class="headerlink" title="基于BST实现"></a>基于BST实现</h3><h4 id="节点结构"><a href="#节点结构" class="headerlink" title="节点结构"></a>节点结构</h4><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> T&gt;</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">AVLTreeNode</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    AVLTreeNode(T value, AVLTreeNode&lt;T&gt;*l, AVLTreeNode&lt;T&gt;*r)</span><br><span class="line">    :key(value), lchild(l), rchild(r)&#123;&#125;</span><br><span class="line"></span><br><span class="line">    T key;<span class="comment">//节点的值</span></span><br><span class="line">    <span class="keyword">int</span> height;<span class="comment">//节点高度，用于计算平衡因子BF</span></span><br><span class="line">    AVLTreeNode&lt;T&gt;* lchild;</span><br><span class="line">    AVLTreeNode&lt;T&gt;* rchild;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>​    在另外一些AVL实现的节点设计方案中，会把BF作为结点的一个属性存储起来，而在这里我们存储的是节点的高度，通过节点的高度我们也可以间接计算出节点的BF。例如节点A的左孩子的height = 2,右孩子的height = 1,那么节点A的平衡因子为2 - 1 = 1.</p>
<h4 id="ADT实现"><a href="#ADT实现" class="headerlink" title="ADT实现"></a>ADT实现</h4><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">template</span>&lt;<span class="keyword">typename</span> T&gt;</span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">AVLTree</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    AVLTree();            <span class="comment">//构造函数</span></span><br><span class="line">    ~AVLTree();            <span class="comment">//析构函数</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">preOrder</span><span class="params">()</span></span>;    <span class="comment">//前序遍历AVL树</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">InOrder</span><span class="params">()</span></span>;        <span class="comment">//中序遍历AVL树   </span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">postOrder</span><span class="params">()</span></span>;    <span class="comment">//后序遍历AVL树</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">print</span><span class="params">()</span></span>;        <span class="comment">//打印AVL树</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">destory</span><span class="params">()</span></span>;        <span class="comment">//销毁AVL树</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">insert</span><span class="params">(T key)</span></span>;    <span class="comment">//插入指定值的节点</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">remove</span><span class="params">(T key)</span></span>;    <span class="comment">//移除指定值的节点</span></span><br><span class="line"></span><br><span class="line">    <span class="function">AVLTreeNode&lt;T&gt;* <span class="title">search_recurse</span><span class="params">(T key)</span></span>;    <span class="comment">//利用递归算法进行指定值的查找</span></span><br><span class="line">    <span class="function">AVLTreeNode&lt;T&gt;* <span class="title">search_iterator</span><span class="params">(T key)</span></span>;    <span class="comment">//利用迭代算法进行指定值的查找</span></span><br><span class="line">    <span class="function">T <span class="title">minimum</span><span class="params">()</span></span>;        <span class="comment">//返回AVL中的最小值</span></span><br><span class="line">    <span class="function">T <span class="title">maximum</span><span class="params">()</span></span>;        <span class="comment">//返回AVL中的最大值</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">height</span><span class="params">()</span></span>;        <span class="comment">//返回树的高度</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">    AVLTreeNode&lt;T&gt;* root;    <span class="comment">//AVL树的根节点</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">preOrder</span><span class="params">(AVLTreeNode&lt;T&gt;* pnode)</span> <span class="keyword">const</span></span>;</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">inOrder</span><span class="params">(AVLTreeNode&lt;T&gt;* pnode)</span> <span class="keyword">const</span></span>;</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">postOrder</span><span class="params">(AVLTreeNode&lt;T&gt;* pnode)</span> <span class="keyword">const</span></span>;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">print</span><span class="params">(AVLTreeNode&lt;T&gt;* pnode,T key, <span class="keyword">int</span> direction)</span> <span class="keyword">const</span></span>;</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">destory</span><span class="params">(AVLTreeNode&lt;T&gt;* &amp; pnode)</span></span>;</span><br><span class="line"></span><br><span class="line">    <span class="function">AVLTreeNode&lt;T&gt;* <span class="title">insert</span><span class="params">(AVLTreeNode&lt;T&gt;* &amp;pnode, T key)</span></span>;       </span><br><span class="line">    <span class="function">AVLTreeNode&lt;T&gt;* <span class="title">remove</span><span class="params">(AVLTreeNode&lt;T&gt;* &amp; pnode, AVLTreeNode&lt;T&gt;* pdel)</span></span>; <span class="comment">//删除AVL树中节点pdel，并返回被删除的节点</span></span><br><span class="line"></span><br><span class="line">    <span class="function">AVLTreeNode&lt;T&gt;* <span class="title">minimum</span><span class="params">(AVLTreeNode&lt;T&gt;*pnode)</span><span class="keyword">const</span></span>;</span><br><span class="line">    <span class="function">AVLTreeNode&lt;T&gt;* <span class="title">maximum</span><span class="params">(AVLTreeNode&lt;T&gt;*pnode)</span><span class="keyword">const</span></span>;</span><br><span class="line"></span><br><span class="line">    <span class="function">AVLTreeNode&lt;T&gt;* <span class="title">search_recurse</span><span class="params">(AVLTreeNode&lt;T&gt;* pnode, T key)</span> <span class="keyword">const</span></span>;</span><br><span class="line">    <span class="function">AVLTreeNode&lt;T&gt;* <span class="title">search_iterator</span><span class="params">(AVLTreeNode&lt;T&gt;* pnode, T key)</span> <span class="keyword">const</span></span>;</span><br><span class="line"></span><br><span class="line">    <span class="function">AVLTreeNode&lt;T&gt;* <span class="title">leftRotation</span><span class="params">(AVLTreeNode&lt;T&gt;* pnode)</span></span>;        <span class="comment">//单旋:左旋操作</span></span><br><span class="line">    <span class="function">AVLTreeNode&lt;T&gt;* <span class="title">rightRotation</span><span class="params">(AVLTreeNode&lt;T&gt;* pnode)</span></span>;        <span class="comment">//单旋:右旋操作</span></span><br><span class="line">    <span class="function">AVLTreeNode&lt;T&gt;* <span class="title">leftRightRotation</span><span class="params">(AVLTreeNode&lt;T&gt;* pnode)</span></span>;    <span class="comment">//双旋:先左旋后右旋操作</span></span><br><span class="line">    <span class="function">AVLTreeNode&lt;T&gt;* <span class="title">rightLeftRotation</span><span class="params">(AVLTreeNode&lt;T&gt;* pnode)</span></span>;    <span class="comment">//双旋:先右旋后左旋操作</span></span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>旋转操作(rotation)用来调整失去平衡的二叉树，四个内部接口针对四种失衡情况进行调整。</p>
<p>操作的外部接口与内部实现接口。例如 preOrder()为提供给用户使用的接口，接口声明为public；而preOrder(AVLTreeNode* pnode)是类内部为了递归操作所使用的接口，接口声明为private。</p>
<p>详细代码：<a target="_blank" rel="noopener" href="https://github.com/huanzheWu/Data-Structure/blob/master/AVLTree/AVLTree/AVLTree.h">https://github.com/huanzheWu/Data-Structure/blob/master/AVLTree/AVLTree/AVLTree.h</a></p>
<p>作者：huanzheWu</p>
<h2 id="关键操作"><a href="#关键操作" class="headerlink" title="关键操作"></a>关键操作</h2><p>关键是对AVL树进行节点的插入或删除都有可能导致AVL失去平衡，所以对AVL进行平衡调整（树旋转）是AVL树的核心操作。</p>
<h4 id="单向左旋"><a href="#单向左旋" class="headerlink" title="单向左旋"></a>单向左旋</h4><p>当我们<strong>在右子树插入右孩子导致AVL失衡</strong>时，我们需要进行<strong>单左旋</strong>调整。旋转围绕最小失衡子树的根节点进行。</p>
<p>在删除新节点时也有可能会出现需要单左旋的情况。</p>
<p>首先插入{4，5，6}，在插入元素6后出现不平衡的情况：</p>
<p><img src="https://i.loli.net/2021/04/14/Vg9KH5QuwEo6I41.png" alt="AVL_2.png"></p>
<p>左旋代码：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">template</span>&lt;<span class="keyword">typename</span> T&gt;</span><br><span class="line">AVLTreeNode&lt;T&gt;* AVLTree&lt;T&gt;::leftRotation(AVLTreeNode&lt;T&gt;* proot)</span><br><span class="line">&#123;</span><br><span class="line">    AVLTreeNode&lt;T&gt;* prchild = proot-&gt;rchild;<span class="comment">//proot为最小失衡子树根节点</span></span><br><span class="line">    proot-&gt;rchild = prchild-&gt;lchild;</span><br><span class="line">    prchild-&gt;lchild = proot;</span><br><span class="line"></span><br><span class="line">    proot-&gt;height = max(height(proot-&gt;lchild),height(proot-&gt;rchild))+<span class="number">1</span>;     <span class="comment">//更新节点的高度值</span></span><br><span class="line">    prchild-&gt;height = max(height(prchild-&gt;lchild), height(prchild-&gt;rchild)) + <span class="number">1</span>; <span class="comment">//更新节点的高度值</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> prchild;                    </span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<ol>
<li>参数proot为最小失衡子树的根节点，在图四中为节点4</li>
<li>若节点5有左子树，则该左子树成为节点4的右子树</li>
<li>节点4成为节点5的左子树</li>
<li>最后更新节点的高度值</li>
</ol>
<h4 id="先左旋后右旋"><a href="#先左旋后右旋" class="headerlink" title="先左旋后右旋"></a>先左旋后右旋</h4><p><img src="https://i.loli.net/2021/04/14/Sg9yurwdxULeD2k.png" alt="AVL_3.png"></p>
<p>需要进行两次旋转的原因是第一次旋转后，AVL树仍旧处于不平衡的状态，第二次旋转再次进行调整。<br>我们继续插入元素{8，7}:</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">template</span>&lt;<span class="keyword">typename</span> T&gt;</span><br><span class="line">AVLTreeNode&lt;T&gt;* AVLTree&lt;T&gt;::rightLeftRotation(AVLTreeNode&lt;T&gt;* proot)</span><br><span class="line">&#123;</span><br><span class="line">    proot-&gt;rchild = rightRotation(proot-&gt;rchild);</span><br><span class="line">    <span class="keyword">return</span> leftRotation(proot);</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<ol>
<li>首先对最小不平衡子树的根节点（也就是节点6）的右孩子（也就是8）进行右旋操作</li>
<li>再对节点6进行一次左旋操作</li>
</ol>
<p>左左和右右的情况下，只需要进行一次旋转操作；在左右和右左的情况下，需要进行两次旋转操作。</p>
<h3 id="基本操作"><a href="#基本操作" class="headerlink" title="基本操作"></a>基本操作</h3><table>
<thead>
<tr>
<th>算法</th>
<th></th>
<th><strong>平均</strong></th>
<th><strong>最差</strong></th>
</tr>
</thead>
<tbody><tr>
<td>空间</td>
<td></td>
<td>O(n)</td>
<td>O(n)</td>
</tr>
<tr>
<td>搜索</td>
<td></td>
<td>O(log n)</td>
<td>O(log n)</td>
</tr>
<tr>
<td>插入</td>
<td></td>
<td>O(log n)</td>
<td>O(log n)</td>
</tr>
<tr>
<td>删除</td>
<td></td>
<td>O(log n)</td>
<td>O(log n)</td>
</tr>
</tbody></table>
<h3 id="AVL节点计算"><a href="#AVL节点计算" class="headerlink" title="AVL节点计算"></a>AVL节点计算</h3><p>wiki：</p>
<p>留</p>
<h2 id="应用"><a href="#应用" class="headerlink" title="应用"></a>应用</h2><p>AVL树是带有平衡条件的二叉查找树,一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡,左右子树树高不超过1,和红黑树相比,它是严格的平衡二叉树,平衡条件必须满足(所有节点的左右子树高度差不超过1).不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡,而旋转是非常耗时的,由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。</p>
<p>由于维护这种高度平衡所付出的代价比从中获得的效率收益还大,故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树.当然,如果应用场景中对插入删除不频繁,只是对查找要求较高,那么AVL还是较优于红黑树.</p>
<p>Windows NT内核中广泛存在。</p>
<h1 id="Heaps"><a href="#Heaps" class="headerlink" title="Heaps"></a>Heaps</h1><h1 id="binomial-heap二项式堆"><a href="#binomial-heap二项式堆" class="headerlink" title="binomial heap二项式堆"></a>binomial heap二项式堆</h1><p><strong>二项堆</strong>（binomial heap）是一种类似于<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E5%A0%86">二叉堆</a>的<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/%E5%A0%86_(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84)">堆结构</a>。与二叉堆相比，其优势是可以快速合并两个堆，因此它属于可合并堆（mergeable heap）<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/%E6%8A%BD%E8%B1%A1%E6%95%B8%E6%93%9A%E9%A1%9E%E5%9E%8B">抽象数据类型</a>的一种。</p>
<p>二项树递归定义如下：</p>
<ul>
<li>度数为0的二项树只包含一个结点</li>
<li>度数为k的二项树有一个根结点，根结点下有k个子女，每个子女分别是度数分别为k-1,k-2,……,2,1,0的二项树的根</li>
</ul>
<p><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Binomial_Trees.svg/500px-Binomial_Trees.svg.png" alt="img"></p>
<p>度数为k的二项树共有$2^k$个结点，高度为k。在深度d处有$\tbinom {k}{d}$(二项式系数k取d)个结点。</p>
<p>二项堆是指满足以下性质的二项树的集合：</p>
<ul>
<li>每棵二项树都满足最小堆性质，即结点关键字大于等于其父结点的值</li>
<li>不能有两棵或以上的二项树有相同度数（包括度数为0）。换句话说，具有度数k的二项树有0个或1个。</li>
</ul>
<p>以上第一个性质保证了二项树的根结点包含了最小的关键字。第二个性质则说明结点数为n的二项堆最多只有$\log {n}$棵二项树。实际上，包含n个节点的二项堆的构成情况，由n的二进制表示唯一确定，其中每一位对应于一颗二项树。例如，13的二进制表示为1101,$2^{3}+2^{2}+2^{0}$, 因此具有13个节点的二项堆由度数为3, 2, 0的三棵二项树组成：</p>
<p>13个节点的二项堆：</p>
<p><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/6/61/Binomial-heap-13.svg/325px-Binomial-heap-13.svg.png" alt="Example of a binomial heap"></p>
<h2 id="数据结构-1"><a href="#数据结构-1" class="headerlink" title="数据结构"></a>数据结构</h2><p>由于并不需要对二项树的根结点进行随机存取，因而这些结点可以存成链表结构。</p>
<h3 id="二项树ADT"><a href="#二项树ADT" class="headerlink" title="二项树ADT"></a>二项树ADT</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Tree</span> &#123;</span></span><br><span class="line">      <span class="keyword">public</span>:</span><br><span class="line">        <span class="comment">// Constructors.构造函数</span></span><br><span class="line">        Tree();</span><br><span class="line">        Tree(<span class="keyword">int</span> size);</span><br><span class="line">        Tree(<span class="keyword">int</span> size, <span class="keyword">int</span> value);</span><br><span class="line">        Tree(<span class="keyword">const</span> Tree&amp;);</span><br><span class="line"></span><br><span class="line">        <span class="comment">// Destructor.析构函数</span></span><br><span class="line">        <span class="keyword">virtual</span> ~Tree();</span><br><span class="line">		<span class="comment">//返回节点值</span></span><br><span class="line">        <span class="function"><span class="keyword">int</span> <span class="title">getValue</span><span class="params">()</span> <span class="keyword">const</span></span>;</span><br><span class="line">    	<span class="comment">//返回树的大小</span></span><br><span class="line">        <span class="function"><span class="keyword">int</span> <span class="title">getSize</span><span class="params">()</span> <span class="keyword">const</span></span>;</span><br><span class="line">    	<span class="comment">//返回子树</span></span><br><span class="line">        <span class="function">Tree* <span class="title">getChilderen</span><span class="params">()</span> <span class="keyword">const</span></span>;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">void</span> <span class="title">setValue</span><span class="params">(<span class="keyword">int</span> value)</span></span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// Deep copy of tree. Needs the same size.</span></span><br><span class="line">    	<span class="comment">//深拷贝树</span></span><br><span class="line">        Tree&amp; <span class="keyword">operator</span>=(<span class="keyword">const</span> Tree&amp; tree);</span><br><span class="line"></span><br><span class="line">        <span class="comment">// Check if the size, value and (recursively) childeren are equal.</span></span><br><span class="line">    	<span class="comment">//检查大小，值，与（递归地）孩子是否平衡</span></span><br><span class="line">        <span class="keyword">bool</span> <span class="keyword">operator</span>==(<span class="keyword">const</span> Tree&amp; tree) <span class="keyword">const</span>;</span><br><span class="line">        <span class="keyword">bool</span> <span class="keyword">operator</span>!=(<span class="keyword">const</span> Tree&amp; tree) <span class="keyword">const</span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// The merge of two tree of the same size.</span></span><br><span class="line">    	<span class="comment">//合并2个相同的树</span></span><br><span class="line">        <span class="keyword">friend</span> <span class="keyword">const</span> Tree <span class="keyword">operator</span>+(<span class="keyword">const</span> Tree&amp; tree1, <span class="keyword">const</span> Tree&amp; Tree2);</span><br><span class="line"></span><br><span class="line">        <span class="comment">// Debugging</span></span><br><span class="line">        <span class="function"><span class="keyword">void</span> <span class="title">print</span><span class="params">()</span> <span class="keyword">const</span></span>;</span><br><span class="line">        <span class="function"><span class="keyword">void</span> <span class="title">printr</span><span class="params">(<span class="keyword">int</span> prefix)</span> <span class="keyword">const</span></span>;</span><br><span class="line"></span><br><span class="line">      <span class="keyword">private</span>:</span><br><span class="line"></span><br><span class="line">        <span class="comment">// The size of the tree. This is the order of the tree.</span></span><br><span class="line">    	<span class="comment">//树的大小</span></span><br><span class="line">        <span class="keyword">int</span> size;</span><br><span class="line">        <span class="comment">// The value of the root node.</span></span><br><span class="line">        <span class="keyword">int</span> value;</span><br><span class="line">        <span class="comment">// An array of the childeren of this Trees root.</span></span><br><span class="line">        Tree* childeren;</span><br><span class="line"></span><br><span class="line">    &#125;;</span><br><span class="line"><span class="comment">//叶节点类</span></span><br><span class="line">	<span class="class"><span class="keyword">class</span> <span class="title">Leaf</span> :</span> <span class="keyword">public</span> Tree &#123;</span><br><span class="line">	  <span class="keyword">public</span>:</span><br><span class="line">		Leaf();</span><br><span class="line">		Leaf(<span class="keyword">const</span> <span class="keyword">int</span> value);</span><br><span class="line"></span><br><span class="line">	&#125;;</span><br></pre></td></tr></table></figure>

<h3 id="二项堆ADT"><a href="#二项堆ADT" class="headerlink" title="二项堆ADT"></a>二项堆ADT</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Heap</span> &#123;</span></span><br><span class="line"></span><br><span class="line">      <span class="keyword">public</span>:</span><br><span class="line"></span><br><span class="line">        Heap();</span><br><span class="line">        ~Heap();</span><br><span class="line"></span><br><span class="line">        <span class="comment">// Print each tree in the heap.</span></span><br><span class="line">    	<span class="comment">//打印堆中的各个树</span></span><br><span class="line">        <span class="function"><span class="keyword">void</span> <span class="title">print</span><span class="params">()</span> <span class="keyword">const</span></span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// Pushing a new value onto the heap.</span></span><br><span class="line">    	<span class="comment">//将新值推入堆。</span></span><br><span class="line">        <span class="function"><span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">const</span> <span class="keyword">int</span> value)</span></span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// Taking the smallest value off the heap.</span></span><br><span class="line">    	<span class="comment">//从堆中取出最小的值。</span></span><br><span class="line">        <span class="function"><span class="keyword">int</span> <span class="title">pop</span><span class="params">()</span></span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// Merge another heap with this one.</span></span><br><span class="line">    	<span class="comment">//合并另外一个堆</span></span><br><span class="line">        Heap&amp; <span class="keyword">operator</span>+=(<span class="keyword">const</span> Heap&amp; heap);</span><br><span class="line"></span><br><span class="line">      <span class="keyword">private</span>:</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> size;</span><br><span class="line">        Tree* trees;</span><br><span class="line">        <span class="keyword">bool</span>* used;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// Merge a single tree into this heap.</span></span><br><span class="line">    	<span class="comment">//合并一个树到堆中</span></span><br><span class="line">        <span class="function"><span class="keyword">void</span> <span class="title">merge</span><span class="params">(<span class="keyword">const</span> Tree&amp; tree)</span></span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// Grow the number of trees this heap holds.</span></span><br><span class="line">    	<span class="comment">//添加堆所有的树个数</span></span><br><span class="line">        <span class="function"><span class="keyword">void</span> <span class="title">grow</span><span class="params">(<span class="keyword">const</span> <span class="keyword">int</span> min_size)</span></span>;</span><br><span class="line">    &#125;;</span><br></pre></td></tr></table></figure>

<h3 id="主要操作"><a href="#主要操作" class="headerlink" title="主要操作"></a>主要操作</h3><p>合并</p>
<p>最基本的为二个分支度相同的二项树的合并。由于二项树根节点包含最小的关键字，因此在二棵树合并时，只需比较二个根节点关键字的大小，其中含小关键字的节点成为结果树的根节点，另一棵树则变成结果树的子树。</p>
<p><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/9/9f/Binomial_heap_merge1.svg/200px-Binomial_heap_merge1.svg.png" alt="img"></p>
<p>两个二项堆的合并则可按如下步骤进行：分支度j从小取到大，在两个二项堆中如果其中只有一棵树的分支度为j，即将此树移动到结果堆，而如果只两棵树的分支度都为j，则根据以上方法合并为一个分支度为j+1,的二项树。此后这个分支度为j+1的二项树。此后这个分支度为j+1的树可能会和其他分支度为j+1的树合并,因此，对于任何分支度j,可能最多需要合并3棵二项树。此操作的时间复杂度为$O(logn)$。</p>
<h2 id="应用-1"><a href="#应用-1" class="headerlink" title="应用"></a>应用</h2><p>当堆需要合并操作时，不满足O(N)的效率。二叉堆合并只能把节点一个个插入。</p>
<p>但是使其变成了松散的结构，所以应用更多的是斐波拉契堆(对于二项堆优化,然而实际应用也不多,实现太过困难)。</p>
<p>图</p>
<h1 id="Trie字典树"><a href="#Trie字典树" class="headerlink" title="Trie字典树"></a>Trie字典树</h1><h2 id="字典树"><a href="#字典树" class="headerlink" title="字典树"></a>字典树</h2><p>trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。trie中的键通常是字符串，但也可以是其它的结构。trie的算法可以很容易地修改为处理其它结构的有序序列，比如一串数字或者形状的排列。比如，<strong>bitwise trie</strong>中的键是一串比特，可以用于表示整数或者内存地址。键不需要被显式地保存在节点中。图示中标注出完整的单词，只是为了演示trie的原理。</p>
<p>trie一般用矩阵表示。行表示状态，列表示输入字符，（行，列）位置表示转移状态。这种方式的查询效率很高，但由于稀疏的现象严重，空间利用效率很低。也可以采用压缩的存储方式即链表来表示状态转移，但由于要线性查询，会造成效率低下。于是人们提出了下面两种结构。</p>
<h3 id="三数组Trie"><a href="#三数组Trie" class="headerlink" title="三数组Trie"></a>三数组Trie</h3><p>三数组Trie（Triple-Array Trie）结构包括三个数组：base,next和check.</p>
<h3 id="二数组Trie"><a href="#二数组Trie" class="headerlink" title="二数组Trie"></a>二数组Trie</h3><p>二数组Trie（Double-Array Trie）包含base和check两个数组。base数组的每个元素表示一个Trie节点，即一个状态；check数组表示某个状态的前驱状态。</p>
<p>Trie 树是一棵多叉树，只要先序遍历整棵树，输出相应的字符串，便是按字典序排序的结果。</p>
<h2 id="后缀树"><a href="#后缀树" class="headerlink" title="后缀树"></a>后缀树</h2><p><strong>后缀树</strong>（Suffix tree）是一种数据结构，能快速解决很多关于字符串的问题。后缀树的概念最早由Weiner于1973年提出，既而由McCreight在1976年和Ukkonen在1992年和1995年加以改进完善。一个string S的后缀树是一个边（edge）被标记为字符串的树。因此每一个S的后缀都唯一对应一条从根节点到叶节点的路径。这样就形成了一个S的后缀的<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%A0%91">基数树</a>（radix tree）。后缀树是<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/%E5%89%8D%E7%BC%80%E6%A0%91">前缀树</a>（trie）里的一个特殊类型。</p>
<p><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Suffix_tree_BANANA.svg/250px-Suffix_tree_BANANA.svg.png" alt="img"></p>
<p>单词BANANA的后缀树，$为终止符，叶子节点中的数据代表出现的起点位置,后缀链用点线画出。</p>
<h2 id="数据结构-2"><a href="#数据结构-2" class="headerlink" title="数据结构"></a>数据结构</h2><p>使用链表来实现Trie字典树，字符串的每个字符作为一个Node节点，Node主要有两部分组成：</p>
<ol>
<li>是否是单词 (boolean isWord)</li>
<li>节点所有的子节点，用map来保存 (Map next)</li>
</ol>
<p>例如插入一个<strong>paint</strong>单词，如果用户查询<strong>pain</strong>，尽管 <strong>paint</strong> 包含了 <strong>pain</strong>，但是Trie中仍然不包含 <strong>pain</strong> 这个单词，所以如果往Trie中插入一个单词，需要把该单词的最后一个字符的节点的 <strong>isWord</strong> 设置为 <strong>true</strong>。所以为什么Node需要存储 <strong>是否是单词</strong> 这个属性。</p>
<p>节点的所有子节点，通过一个Map来存储，key是当前子节点对应的字符，value是子节点。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">add</span><span class="params">(String word)</span> </span>&#123;</span><br><span class="line">	Node current = root;</span><br><span class="line">	<span class="keyword">char</span>[] cs = word.toCharArray();</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">char</span> c : cs) &#123;</span><br><span class="line">		Node next = current.next.get(c);</span><br><span class="line">		<span class="keyword">if</span> (next == <span class="keyword">null</span>) &#123;</span><br><span class="line">		    <span class="comment">//一个字符对应一个Node节点</span></span><br><span class="line">			current.next.put(c, <span class="keyword">new</span> Node());</span><br><span class="line">		&#125;</span><br><span class="line">		current = current.next.get(c);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">//current就是word的最后一个字符的Node</span></span><br><span class="line">	</span><br><span class="line">	<span class="comment">//如果当前的node已经是一个word，则不需要添加</span></span><br><span class="line">	<span class="keyword">if</span> (!current.isWord) &#123;</span><br><span class="line">		size++;</span><br><span class="line">		current.isWord = <span class="keyword">true</span>;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="查找"><a href="#查找" class="headerlink" title="查找"></a>查找</h3><p>Trie查找操作就比较简单了，遍历带查找的字符串的字符，如果每个节点都存在，并且待查找字符串的最后一个字符对应的Node的 <strong>isWord</strong> 属性为 <strong>true</strong> ，则表示该单词存在，伪代码如下：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">contains</span><span class="params">(String word)</span> </span>&#123;</span><br><span class="line">	Node current = root;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; word.length(); i++) &#123;</span><br><span class="line">		<span class="keyword">char</span> c = word.charAt(i);</span><br><span class="line">		Node node = current.next.get(c);</span><br><span class="line">		<span class="keyword">if</span> (node == <span class="keyword">null</span>) &#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		current = node;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">//current就是word的最后一个字符的Node</span></span><br><span class="line">	<span class="keyword">return</span> current.isWord;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="前缀查询"><a href="#前缀查询" class="headerlink" title="前缀查询"></a>前缀查询</h3><p>前缀查询和上面的查询操作基本类似，就是不需要判断 <strong>isWord</strong> 了</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">containsPrefix</span><span class="params">(String prefix)</span> </span>&#123;</span><br><span class="line">    Node current = root;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; prefix.length(); i++) &#123;</span><br><span class="line">        <span class="keyword">char</span> c = prefix.charAt(i);</span><br><span class="line">        Node node = current.next.get(c);</span><br><span class="line">        <span class="keyword">if</span> (node == <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        current = node;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="删除"><a href="#删除" class="headerlink" title="删除"></a>删除</h3><p>Trie的删除操作就稍微复杂一些，主要分为以下3种情况：</p>
<h4 id="如果单词是另一个单词的前缀"><a href="#如果单词是另一个单词的前缀" class="headerlink" title="如果单词是另一个单词的前缀"></a>如果单词是另一个单词的前缀</h4><p>如果待删除的单词是另一个单词的前缀，只需要把该单词的最后一个节点的 <strong>isWord</strong> 的改成false</p>
<p>比如Trie中存在 <strong>panda</strong> 和 <strong>pan</strong> 这两个单词，删除 <strong>pan</strong> ，只需要把字符 <strong>n</strong> 对应的节点的 <strong>isWord</strong> 改成 <strong>false</strong> 即可</p>
<h4 id="如果单词的所有字母的都没有多个分支，删除整个单词"><a href="#如果单词的所有字母的都没有多个分支，删除整个单词" class="headerlink" title="如果单词的所有字母的都没有多个分支，删除整个单词"></a>如果单词的所有字母的都没有多个分支，删除整个单词</h4><p>如果单词的所有字母的都没有多个分支（也就是说该单词所有的字符对应的Node都只有一个子节点），则删除整个单词</p>
<p>例如要删除如下图的<strong>see</strong>单词，如下图所示：</p>
<h4 id="如果单词的除了最后一个字母，其他的字母有多个分支"><a href="#如果单词的除了最后一个字母，其他的字母有多个分支" class="headerlink" title="如果单词的除了最后一个字母，其他的字母有多个分支"></a>如果单词的除了最后一个字母，其他的字母有多个分支</h4><p><img src="https://i.loli.net/2021/04/14/niDsg7rYXcMVBRq.png" alt="TRIE_1.png"></p>
<p>ADT实现</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Trie</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> Node root;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> size;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span> </span>&#123;</span><br><span class="line">        <span class="keyword">public</span> <span class="keyword">boolean</span> isWord;</span><br><span class="line">        <span class="keyword">public</span> Map&lt;Character, Node&gt; next;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            next = <span class="keyword">new</span> TreeMap&lt;&gt;();</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">(<span class="keyword">boolean</span> isWord)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">this</span>();</span><br><span class="line">            <span class="keyword">this</span>.isWord = isWord;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Trie</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        root = <span class="keyword">new</span> Node();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">size</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> size;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> size == <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 插入操作</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> word 单词</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">add</span><span class="params">(String word)</span> </span>&#123;</span><br><span class="line">        Node current = root;</span><br><span class="line">        <span class="keyword">char</span>[] cs = word.toCharArray();</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">char</span> c : cs) &#123;</span><br><span class="line">            Node next = current.next.get(c);</span><br><span class="line">            <span class="keyword">if</span> (next == <span class="keyword">null</span>) &#123;</span><br><span class="line">                current.next.put(c, <span class="keyword">new</span> Node());</span><br><span class="line">            &#125;</span><br><span class="line">            current = current.next.get(c);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//如果当前的node已经是一个word，则不需要添加</span></span><br><span class="line">        <span class="keyword">if</span> (!current.isWord) &#123;</span><br><span class="line">            size++;</span><br><span class="line">            current.isWord = <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 是否包含某个单词</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> word 单词</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> 存在返回true，反之false</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">contains</span><span class="params">(String word)</span> </span>&#123;</span><br><span class="line">        Node current = root;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; word.length(); i++) &#123;</span><br><span class="line">            <span class="keyword">char</span> c = word.charAt(i);</span><br><span class="line">            Node node = current.next.get(c);</span><br><span class="line">            <span class="keyword">if</span> (node == <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            current = node;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//如果只存在 panda这个词，查询 pan，虽然有这3个字母，但是并不存在该单词</span></span><br><span class="line">        <span class="keyword">return</span> current.isWord;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Trie是否包含某个前缀</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> prefix 前缀</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">containsPrefix</span><span class="params">(String prefix)</span> </span>&#123;</span><br><span class="line">        Node current = root;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; prefix.length(); i++) &#123;</span><br><span class="line">            <span class="keyword">char</span> c = prefix.charAt(i);</span><br><span class="line">            Node node = current.next.get(c);</span><br><span class="line">            <span class="keyword">if</span> (node == <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            current = node;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * 1，如果单词是另一个单词的前缀，只需要把该word的最后一个节点的isWord的改成false</span></span><br><span class="line"><span class="comment">     * 2，如果单词的所有字母的都没有多个分支，删除整个单词</span></span><br><span class="line"><span class="comment">     * 3，如果单词的除了最后一个字母，其他的字母有多个分支，</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 删除操作</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> word</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">remove</span><span class="params">(String word)</span> </span>&#123;</span><br><span class="line">        Node multiChildNode = <span class="keyword">null</span>;</span><br><span class="line">        <span class="keyword">int</span> multiChildNodeIndex = -<span class="number">1</span>;</span><br><span class="line">        Node current = root;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; word.length(); i++) &#123;</span><br><span class="line">            Node child = current.next.get(word.charAt(i));</span><br><span class="line">            <span class="comment">//如果Trie中没有这个单词</span></span><br><span class="line">            <span class="keyword">if</span> (child == <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">//当前节点的子节点大于1个</span></span><br><span class="line">            <span class="keyword">if</span> (child.next.size() &gt; <span class="number">1</span>) &#123;</span><br><span class="line">                multiChildNodeIndex = i;</span><br><span class="line">                multiChildNode = child;</span><br><span class="line">            &#125;</span><br><span class="line">            current = child;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//如果单词后面还有子节点</span></span><br><span class="line">        <span class="keyword">if</span> (current.next.size() &gt; <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (current.isWord) &#123;</span><br><span class="line">                current.isWord = <span class="keyword">false</span>;</span><br><span class="line">                size--;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">//不存在该单词，该单词只是前缀</span></span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//如果单词的所有字母的都没有多个分支，删除整个单词</span></span><br><span class="line">        <span class="keyword">if</span> (multiChildNodeIndex == -<span class="number">1</span>) &#123;</span><br><span class="line">            root.next.remove(word.charAt(<span class="number">0</span>));</span><br><span class="line">            size--;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//如果单词的除了最后一个字母，其他的字母有分支</span></span><br><span class="line">        <span class="keyword">if</span> (multiChildNodeIndex != word.length() - <span class="number">1</span>) &#123;</span><br><span class="line">            multiChildNode.next.remove(word.charAt(multiChildNodeIndex + <span class="number">1</span>));</span><br><span class="line">            size--;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h2 id="应用-2"><a href="#应用-2" class="headerlink" title="应用"></a>应用</h2><p>Trie查询效率非常高，但是对空间的消耗还是挺大的，这也是典型的空间换时间。</p>
<p>可以使用 <strong>压缩字典树(Compressed Trie)</strong> ，但是维护相对来说复杂一些。</p>
<p>如果我们不止存储英文单词，还有其他特殊字符，那么维护子节点的集合可能会更多。</p>
<p>可以对Trie字典树做些限制，比如每个节点只能有3个子节点，左边的节点是小于父节点的，中间的节点是等于父节点的，右边的子节点是大于父节点的，这就是**三分搜索Trie字典树(Ternary Search Trie)**。</p>
<p>trie的内部结构可以进行高效的压缩，比如有如果“a”-&gt;”b”-&gt;”c”这三个连续的节点（a是b的父节点，b是c的父节点），”a”与”b”这两个节点均只有唯一的子节点，那么就可以很轻易的把”abc”合并为一个节点。在有insert的情况下，trie树也可以合理的split merge内部节点来节约空间。相比于btree-style数据结构，trie的内存使用率高了一大截，因为btree中多数节点也就是半满的状态，很难达到全满。</p>
<h1 id="Spatial-data-pratitioning-trees空间分割树"><a href="#Spatial-data-pratitioning-trees空间分割树" class="headerlink" title="Spatial data pratitioning trees空间分割树"></a>Spatial data pratitioning trees空间分割树</h1><h2 id="线段树"><a href="#线段树" class="headerlink" title="线段树"></a>线段树</h2><p><strong>线段树</strong>（英语：Segment tree）是一种<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%A8%B9">二叉树</a>形数据结构，1977年由Jon Louis Bentley发明,，用以存储<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/%E5%8D%80%E9%96%93">区间</a>或<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/%E7%B7%9A%E6%AE%B5">线段</a>，并且允许快速查询结构内包含某一点的所有区间。</p>
<p>一个包含n个区间的线段树，空间复杂度为O(N)，查询的时间复杂度为$O(logn+k)$，其中k是符合条件的区间数量。</p>
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/d/d1/Segment_tree.svg/420px-Segment_tree.svg.png" alt="img" style="zoom:150%;" />

<p>线段树的结构为一个<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%A8%B9">二叉树</a>，每个节点都代表一个坐标区间，节点N所代表的区间记为Int(N)，则其需符合以下条件：</p>
<ul>
<li>其每一个叶节点，从左到右代表每个单位区间。</li>
<li>其内部节点代表的区间是其两个儿子代表的区间之联集。</li>
<li>每个节点（包含叶子）中有一个存储线段的数据结构。若一个线段S的坐标区间包含Int(N)但不包含Int(parent(N))，则节点N中会存储线段S。</li>
</ul>
<h2 id="数据结构-3"><a href="#数据结构-3" class="headerlink" title="数据结构"></a>数据结构</h2><p>代码链接：<a target="_blank" rel="noopener" href="https://github.com/kartik8800/segTree/blob/master/SegmentTree.h">https://github.com/kartik8800/segTree/blob/master/SegmentTree.h</a></p>
<p>可以数组存储或链表存储</p>
<p>数组举例</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> left(i) (2*i + 1)</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> right(i) (2*i + 2)</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> parent(i) ((i-1)/2)</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;vector&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">template</span>&lt;<span class="class"><span class="keyword">class</span> <span class="title">T</span>&gt;</span></span><br><span class="line"><span class="class"><span class="title">class</span> <span class="title">SegmentTree</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    <span class="keyword">public</span>:</span><br><span class="line">        <span class="comment">//tree constructors.</span></span><br><span class="line">        SegmentTree(<span class="built_in">std</span>::<span class="built_in">vector</span>&lt;T&gt; data, T value, T (*combine)(T obj1, T obj2));</span><br><span class="line">        SegmentTree(T ar[], <span class="keyword">int</span> n, T value, T (*combine)(T obj1, T obj2));</span><br><span class="line">        </span><br><span class="line">        <span class="comment">//query the range l to r, 0 based array indexing.</span></span><br><span class="line">    	<span class="comment">//查询范围l到r，基于0的数组索引。</span></span><br><span class="line">        <span class="function">T <span class="title">query</span><span class="params">(<span class="keyword">int</span> l, <span class="keyword">int</span> r)</span></span>;</span><br><span class="line">        </span><br><span class="line">        <span class="comment">//update the element at index idx to val.</span></span><br><span class="line">    	<span class="comment">//将索引idx处的元素更新为val。</span></span><br><span class="line">        <span class="function"><span class="keyword">void</span> <span class="title">update</span><span class="params">(<span class="keyword">int</span> idx, T val)</span></span>;</span><br><span class="line">        <span class="comment">///TODO lazy propagation</span></span><br><span class="line">    <span class="keyword">private</span>:</span><br><span class="line">        <span class="comment">//represents the segment tree.</span></span><br><span class="line">        T *tree;</span><br><span class="line">    </span><br><span class="line">        <span class="comment">//builds the segment tree.</span></span><br><span class="line">    	<span class="comment">//建线段树</span></span><br><span class="line">        <span class="function"><span class="keyword">void</span> <span class="title">buildTree</span><span class="params">(<span class="built_in">std</span>::<span class="built_in">vector</span>&lt;T&gt; data)</span></span>;</span><br><span class="line">        </span><br><span class="line">        <span class="comment">//size of the segment tree array.</span></span><br><span class="line">    	<span class="comment">//线段树数组大小</span></span><br><span class="line">        <span class="keyword">int</span> segTreeSize;</span><br><span class="line">    </span><br><span class="line">        <span class="comment">//extra nodes must be added to array to make its size a power of 2</span></span><br><span class="line">        <span class="comment">//this is the value to be filled for the those nodes.</span></span><br><span class="line">    	<span class="comment">//数组必须添加额外的节点，使其大小为2的幂</span></span><br><span class="line">    	<span class="comment">//这是要为这些节点填充的值。</span></span><br><span class="line">        T valueForExtraNodes;</span><br><span class="line">    </span><br><span class="line">        <span class="comment">//specifies how to combine child node results to form parent node result.</span></span><br><span class="line">    	<span class="comment">//指定如何将子节点结果组合成父节点结果。</span></span><br><span class="line">        T (*combine)(T obj1, T obj2);</span><br><span class="line">    </span><br><span class="line">        <span class="comment">//used to calculate the size of array needed to store the tree.</span></span><br><span class="line">    	<span class="comment">//用于计算存储树所需数组的大小。</span></span><br><span class="line">        <span class="function"><span class="keyword">int</span> <span class="title">calculateSize</span><span class="params">(<span class="keyword">int</span> n)</span></span>;</span><br><span class="line">    </span><br><span class="line">        <span class="comment">//helps to solve a range query.</span></span><br><span class="line">    	<span class="comment">//帮助解决范围查询。</span></span><br><span class="line">        <span class="function">T <span class="title">queryHelper</span><span class="params">(<span class="keyword">int</span> l,<span class="keyword">int</span> r, <span class="keyword">int</span> st, <span class="keyword">int</span> ed, <span class="keyword">int</span> node)</span></span>;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br></pre></td></tr></table></figure>




    </div>
    
    
    

      <footer class="post-footer">
          
          <div class="post-tags">
              <a href="/tags/C/" rel="tag"><i class="fa fa-tag"></i> C++</a>
          </div>

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/2021/04/14/csapphw1/" rel="prev" title="CSAPP第一次作业">
      <i class="fa fa-chevron-left"></i> CSAPP第一次作业
    </a></div>
      <div class="post-nav-item">
    <a href="/2021/04/14/dslab8/" rel="next" title="一个查找比较试验">
      一个查找比较试验 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#Search-trees"><span class="nav-number">1.</span> <span class="nav-text">Search trees</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#AVL%E6%A0%91"><span class="nav-number">2.</span> <span class="nav-text">AVL树</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%A6%82%E8%BF%B0"><span class="nav-number">2.1.</span> <span class="nav-text">概述</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="nav-number">2.2.</span> <span class="nav-text">数据结构</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%9F%BA%E4%BA%8EBST%E5%AE%9E%E7%8E%B0"><span class="nav-number">2.2.1.</span> <span class="nav-text">基于BST实现</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E8%8A%82%E7%82%B9%E7%BB%93%E6%9E%84"><span class="nav-number">2.2.1.1.</span> <span class="nav-text">节点结构</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#ADT%E5%AE%9E%E7%8E%B0"><span class="nav-number">2.2.1.2.</span> <span class="nav-text">ADT实现</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%85%B3%E9%94%AE%E6%93%8D%E4%BD%9C"><span class="nav-number">2.3.</span> <span class="nav-text">关键操作</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%8D%95%E5%90%91%E5%B7%A6%E6%97%8B"><span class="nav-number">2.3.0.1.</span> <span class="nav-text">单向左旋</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%85%88%E5%B7%A6%E6%97%8B%E5%90%8E%E5%8F%B3%E6%97%8B"><span class="nav-number">2.3.0.2.</span> <span class="nav-text">先左旋后右旋</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%9F%BA%E6%9C%AC%E6%93%8D%E4%BD%9C"><span class="nav-number">2.3.1.</span> <span class="nav-text">基本操作</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#AVL%E8%8A%82%E7%82%B9%E8%AE%A1%E7%AE%97"><span class="nav-number">2.3.2.</span> <span class="nav-text">AVL节点计算</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%BA%94%E7%94%A8"><span class="nav-number">2.4.</span> <span class="nav-text">应用</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#Heaps"><span class="nav-number">3.</span> <span class="nav-text">Heaps</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#binomial-heap%E4%BA%8C%E9%A1%B9%E5%BC%8F%E5%A0%86"><span class="nav-number">4.</span> <span class="nav-text">binomial heap二项式堆</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-1"><span class="nav-number">4.1.</span> <span class="nav-text">数据结构</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BA%8C%E9%A1%B9%E6%A0%91ADT"><span class="nav-number">4.1.1.</span> <span class="nav-text">二项树ADT</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BA%8C%E9%A1%B9%E5%A0%86ADT"><span class="nav-number">4.1.2.</span> <span class="nav-text">二项堆ADT</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%B8%BB%E8%A6%81%E6%93%8D%E4%BD%9C"><span class="nav-number">4.1.3.</span> <span class="nav-text">主要操作</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%BA%94%E7%94%A8-1"><span class="nav-number">4.2.</span> <span class="nav-text">应用</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#Trie%E5%AD%97%E5%85%B8%E6%A0%91"><span class="nav-number">5.</span> <span class="nav-text">Trie字典树</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%AD%97%E5%85%B8%E6%A0%91"><span class="nav-number">5.1.</span> <span class="nav-text">字典树</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%B8%89%E6%95%B0%E7%BB%84Trie"><span class="nav-number">5.1.1.</span> <span class="nav-text">三数组Trie</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BA%8C%E6%95%B0%E7%BB%84Trie"><span class="nav-number">5.1.2.</span> <span class="nav-text">二数组Trie</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%90%8E%E7%BC%80%E6%A0%91"><span class="nav-number">5.2.</span> <span class="nav-text">后缀树</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-2"><span class="nav-number">5.3.</span> <span class="nav-text">数据结构</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%9F%A5%E6%89%BE"><span class="nav-number">5.3.1.</span> <span class="nav-text">查找</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%89%8D%E7%BC%80%E6%9F%A5%E8%AF%A2"><span class="nav-number">5.3.2.</span> <span class="nav-text">前缀查询</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%88%A0%E9%99%A4"><span class="nav-number">5.3.3.</span> <span class="nav-text">删除</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%A6%82%E6%9E%9C%E5%8D%95%E8%AF%8D%E6%98%AF%E5%8F%A6%E4%B8%80%E4%B8%AA%E5%8D%95%E8%AF%8D%E7%9A%84%E5%89%8D%E7%BC%80"><span class="nav-number">5.3.3.1.</span> <span class="nav-text">如果单词是另一个单词的前缀</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%A6%82%E6%9E%9C%E5%8D%95%E8%AF%8D%E7%9A%84%E6%89%80%E6%9C%89%E5%AD%97%E6%AF%8D%E7%9A%84%E9%83%BD%E6%B2%A1%E6%9C%89%E5%A4%9A%E4%B8%AA%E5%88%86%E6%94%AF%EF%BC%8C%E5%88%A0%E9%99%A4%E6%95%B4%E4%B8%AA%E5%8D%95%E8%AF%8D"><span class="nav-number">5.3.3.2.</span> <span class="nav-text">如果单词的所有字母的都没有多个分支，删除整个单词</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%A6%82%E6%9E%9C%E5%8D%95%E8%AF%8D%E7%9A%84%E9%99%A4%E4%BA%86%E6%9C%80%E5%90%8E%E4%B8%80%E4%B8%AA%E5%AD%97%E6%AF%8D%EF%BC%8C%E5%85%B6%E4%BB%96%E7%9A%84%E5%AD%97%E6%AF%8D%E6%9C%89%E5%A4%9A%E4%B8%AA%E5%88%86%E6%94%AF"><span class="nav-number">5.3.3.3.</span> <span class="nav-text">如果单词的除了最后一个字母，其他的字母有多个分支</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%BA%94%E7%94%A8-2"><span class="nav-number">5.4.</span> <span class="nav-text">应用</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#Spatial-data-pratitioning-trees%E7%A9%BA%E9%97%B4%E5%88%86%E5%89%B2%E6%A0%91"><span class="nav-number">6.</span> <span class="nav-text">Spatial data pratitioning trees空间分割树</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%BA%BF%E6%AE%B5%E6%A0%91"><span class="nav-number">6.1.</span> <span class="nav-text">线段树</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-3"><span class="nav-number">6.2.</span> <span class="nav-text">数据结构</span></a></li></ol></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="Sekla"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">Sekla</p>
  <div class="site-description" itemprop="description">Sekla</div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">100</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/categories/">
          
        <span class="site-state-item-count">23</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">14</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
        <a href="https://github.com/ShenTiao" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;ShenTiao" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:584892986@qq.com" title="E-Mail → mailto:584892986@qq.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
  </div>



      </div>

      <iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width=330 height=86 src="//music.163.com/outchain/player?type=2&id=1416875904&auto=0&height=66"></iframe>
      
    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Sekla</span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-chart-area"></i>
    </span>
    <span title="站点总字数">288k</span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
    <span title="站点阅读时长">4:22</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://muse.theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Muse</a> 强力驱动
  </div>

        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    <span class="post-meta-item" id="busuanzi_container_site_uv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item" id="busuanzi_container_site_pv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>








      </div>
    </footer>
  </div>

  
  <script size="300" alpha="0.6" zIndex="-1" src="/lib/canvas-ribbon/canvas-ribbon.js"></script>
  <script src="/lib/anime.min.js"></script>
  <script src="/lib/velocity/velocity.min.js"></script>
  <script src="/lib/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/muse.js"></script>


<script src="/js/next-boot.js"></script>




  















  

  
      

<script>
  if (typeof MathJax === 'undefined') {
    window.MathJax = {
      loader: {
        source: {
          '[tex]/amsCd': '[tex]/amscd',
          '[tex]/AMScd': '[tex]/amscd'
        }
      },
      tex: {
        inlineMath: {'[+]': [['$', '$']]},
        tags: 'ams'
      },
      options: {
        renderActions: {
          findScript: [10, doc => {
            document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
              const display = !!node.type.match(/; *mode=display/);
              const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
              const text = document.createTextNode('');
              node.parentNode.replaceChild(text, node);
              math.start = {node: text, delim: '', n: 0};
              math.end = {node: text, delim: '', n: 0};
              doc.math.push(math);
            });
          }, '', false],
          insertedScript: [200, () => {
            document.querySelectorAll('mjx-container').forEach(node => {
              let target = node.parentNode;
              if (target.nodeName.toLowerCase() === 'li') {
                target.parentNode.classList.add('has-jax');
              }
            });
          }, '', false]
        }
      }
    };
    (function () {
      var script = document.createElement('script');
      script.src = '//cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js';
      script.defer = true;
      document.head.appendChild(script);
    })();
  } else {
    MathJax.startup.document.state(0);
    MathJax.texReset();
    MathJax.typeset();
  }
</script>

    

  

<script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"/live2dw/assets/shizuku.model.json"},"display":{"position":"left","width":250,"height":500},"mobile":{"show":false},"react":{"opacity":0.9},"log":false});</script></body>
</html>

<script type="text/javascript" src="/js/src/love.js"></script>
